子树|损失_55决策树的剪枝算法

篇首语：本文由编程笔记#小编为大家整理，主要介绍了5-5 决策树的剪枝算法相关的知识，希望对你有一定的参考价值。

输入&＃xff1a;
ID3或C4.5的决策树
参数a
输出&＃xff1a;
剪枝后的决策树





T


a




T_a


Ta​

递归版本

1. 从树的根结点开始
2. 如果该结点的孩子中存在子树&＃xff08;不全是叶子结点&＃xff09;&＃xff0c;则先对子树做prune
3. 所有子树都prune之后&＃xff0c;再判断该结点的孩子是否都是叶子
4. 如果不全是叶子&＃xff0c;对该结点的算法结束
5. 如果该结点的孩子都是叶子&＃xff0c;则尝试对该结点剪枝
   5.a 计算
   
   
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   B
   
   
   
   )
   
   
   
   C_a(T_B)
   
   
   Ca​(TB​)&＃xff0c;代表该结点split后以该结点为根结点的子树的损失&＃xff0c;其损失的计算方式与整棵树的计算方式相同
   
   
   
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   B
   
   
   
   )
   
   
   &＃61;
   
   
   
   ∑
   
   
   
   ∣
   
   
   T
   
   
   ∣
   
   
   
   
   
   N
   
   
   t
   
   
   
   
   H
   
   
   t
   
   
   
   (
   
   
   T
   
   
   )
   
   
   &＃43;
   
   
   a
   
   
   ∣
   
   
   T
   
   
   ∣
   
   
   
   C_a(T_B) &＃61; \\sum^|T|N_tH_t(T) &＃43; a|T|
   
   
   Ca​(TB​)&＃61;∑∣T∣​Nt​Ht​(T)&＃43;a∣T∣
   因此在生成树的时候为每个叶子结点保存它的
   
   
   
   
   
   N
   
   
   t
   
   
   
   
   N_t
   
   
   Nt​和
   
   
   
   
   
   H
   
   
   t
   
   
   
   
   H_t
   
   
   Ht​
   5.b 计算
   
   
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   A
   
   
   
   )
   
   
   
   C_a(T_A)
   
   
   Ca​(TA​)&＃xff0c;代表该结点split之前作为一个叶子结点时的熵。因此在生成树时记录该split之前的熵
   5.c 比较
   
   
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   B
   
   
   
   )
   
   
   
   C_a(T_B)
   
   
   Ca​(TB​)和
   
   
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   A
   
   
   
   )
   
   
   
   C_a(T_A)
   
   
   Ca​(TA​)&＃xff0c;如果
   
   
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   A
   
   
   
   )
   
   
   ≤
   
   
   
   C
   
   
   a
   
   
   
   (
   
   
   
   T
   
   
   B
   
   
   
   )
   
   
   
   C_a(T_A)\\le C_a(T_B)
   
   
   Ca​(TA​)≤Ca​(TB​)&＃xff0c;则将该结点修改为叶子结点。即&＃xff1a;计算该结点的输出标记&＃xff0c;并删除它的所有孩子结点。
6. 对该结点的处理结束&＃xff0c;由于这个算法是递归调用的&＃xff0c;如果该结点有父结点&＃xff0c;则要继续处理它的父结点。

def isTree(Node):
return &＃39;child&＃39; in Node.keys()
def Clip(Node):
bestNt &＃61; 0
for value in Node[&＃39;child&＃39;]:
if Node[&＃39;child&＃39;][value][&＃39;Nt&＃39;] > bestNt:
bestNt &＃61; Node[&＃39;child&＃39;][value][&＃39;Nt&＃39;]
bestLabel &＃61; Node[&＃39;child&＃39;][value][&＃39;label&＃39;]
Node[&＃39;label&＃39;] &＃61; bestLabel
Node.pop(&＃39;child&＃39;)

def Merge(Node, alpha):
# 计算CaTb
CT_b &＃61; 0
for value in Node[&＃39;child&＃39;]:
CT_b &＃61; CT_b &＃43; Node[&＃39;child&＃39;][value][&＃39;Nt&＃39;] * Node[&＃39;child&＃39;][value][&＃39;entropy&＃39;] &＃43; alpha
# 计算CaTa
CT_a &＃61; Node[&＃39;entropy&＃39;] &＃43; alpha
# 剪枝的条件
if CT_a <&＃61; CT_b:
Clip(Node)

def prune(Node, alpha):
# 判断子结点中是否存在树
for value in Node[&＃39;child&＃39;]:
# 如果存在树
if isTree(Node[&＃39;child&＃39;][value]):
# 先对树子结点做prune
prune(Node[&＃39;child&＃39;][value], alpha)
# 对所有子树都prune之后&＃xff0c;判断是否所有子树都是叶子
isAllLeaf &＃61; True
for value in Node[&＃39;child&＃39;]:
if isTree(Node[&＃39;child&＃39;][value]):
isAllLeaf &＃61; False
break
# 如果所有子树都是叶子
if isAllLeaf:
# 尝试对结点做剪枝
Merge(Node, alpha)


DP版本

【&＃xff1f;】如何通过DP实现